/*
 * name: mabel xu
 * date: october 26, 2007
 * filename: ap linkedlist free response
 * description: answers to free response practice on linkedlists
 */

public class LinearLinkedLIst
{
	public void makeCircular()
	{
		ListNode current = firstNode;	// pointer starts at first node
		while(current.getNext() != null)	// move pointer to end of list
			current = current.getNext();
		current.setNext(firstNode);		// at end of list, set next to firstNode
	}
	/*	oops doesn't work since it doesn't recurse ... much better though!
	public void reverse()
	{
		// game plan: go through and reverse the pointers ... set first one to point to null, then second to point to first, then third to point to second, etc
		if (this.size() > 1)	// nothing to reverse if 1 or 0 elements in list
		{
			ListNode a = null;			// ListNode for one in question to point to (aka "previous")
			ListNode b = firstNode;		// ListNode to change
			
			// before: a points to "previous" (already changed), b points to "next" (needs to be changed)
			while(b != null)	// keep going through until all are changed
			{
				ListNode temp = b.getNext();	// temporary pointer so "next" of b still accessable
				b.setNext(a);	// reverse the pointer
				a = b;			// advance a
				b = temp;		// advance b
			}	// after: b now points to "previous" and is now called a, b is now the next one (the one that needs changing)
			
			firstNode = a;		// when done, fix the firstNode pointer so it points to the element last changed (the new "first)
		}
	}
	*/
	
	public void reverse()
	{
		if (this.size() > 1)	// only need to reverse if more than 1 element
			reverseHelper(firstNode);
	}
	
	private ListNode reverseHelper(ListNode node)
	{
		if (node.getNext().getNext() != null)
		{
			ListNode a = node;		// the one to be pointed to
			ListNode b = reverseHelper(node.getNext());		// the last one pointed to is the next one to be changed
			b.setNext(a);	// change the one that was the pointer in the previous "iteration"
			return a;		// return last one just pointed to (either for next iteration or for the end)
		}
		else	// when there's 2 nodes left
		{
			ListNode a = node;		// the one to be pointed to
			ListNode b = node.getNext();	// the one to be changed
			b.setNext(a);		// change it
			firstNode = b;		// change firstNode so it points to the "end"
			return a;		// return the one pointed to so it can be changed next
		}
	}
}

